package com.lw.leetcode.arr.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 2008. 出租车的最大盈利
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/24 17:50
 */
public class MaxTaxiEarnings {

    public static void main(String[] args) {
        MaxTaxiEarnings test = new MaxTaxiEarnings();
        // 5
        //[[2,5,4],[1,5,1]]

        int[][] arr = {{2,5,4}, {1,5,1}};
        int k = 5;

        long l = test.maxTaxiEarnings(k, arr);
        System.out.println(l);

    }

    public long maxTaxiEarnings(int n, int[][] rides) {
        Map<Integer, List<Integer>> map = new HashMap<>(n);
        int length = rides.length;
        for (int i = 0; i < length; i++) {
            map.computeIfAbsent(rides[i][1], v -> new ArrayList<>()).add(i);
        }
        long[] arr = new long[n + 1];
        for (int i = 2; i <= n; i++) {
            List<Integer> list = map.get(i);
            arr[i] = arr[i - 1] ;
            if (list != null) {
                for (int index : list) {
                   arr[i] = Math.max(arr[i],arr[rides[index][0]] + i - rides[index][0] + rides[index][2]);
                }
            }
        }
        return arr[n];
    }

}
